package com.LeeCode;

/**
 * 乘积小于 K 的子数组
 */

public class Code713 {
    public static void main(String[] args) {
        int[] nums = {57, 44, 92, 28, 66, 60, 37, 33, 52, 38, 29, 76, 8, 75, 22};
        int k = 18;
        System.out.println(new Code713().numSubarrayProductLessThanK(nums, k));
    }

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;

        int n = nums.length;
        int product = 1;
        int left = 0;
        int ans = 0;

        for (int right = 0; right < n; right++) {
            product *= nums[right];

            // 缩小窗口直到 product < k
            while (product >= k && left <= right) {
                product /= nums[left];
                left++;
            }

            // 所有以 right 结尾的有效子数组：[left...right], ..., [right]
            ans += right - left + 1;
        }

        return ans;
    }
}
